#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	stack<int> st;
	vector<int> vc;
	cin >> n;
	while (n--)
	{
		string s;
		cin >> s;
		if (s == "Push")
		{
			int x;
			cin >> x;
			st.push(x);
			vc.insert(lower_bound(vc.begin(), vc.end(), x), x);
		}
		else {
			if (s == "Pop")
			{
				if (st.empty())
				{
					cout << "Invalid" << endl;
				}
				else {
					cout << st.top() << endl;
					vc.erase(lower_bound(vc.begin(), vc.end(), st.top()));
					st.pop();
				}
			}
			else {
				if (st.empty())
				{
					cout << "Invalid" << endl;
				}
				else {
					int sz = st.size();
					if (sz % 2 == 0)
					{
						cout << vc[sz / 2 - 1] << endl;
					}
					else {
						
						cout << vc[sz / 2] << endl;
					}
				}
			}
		}
		
	}
	return 0;
}

// #include<bits/stdc++.h>
// using namespace std;
// const int N = 1e5+10;
// int stk[N],tt;
// multiset<int> up,down;//默认从小到大排列
// void jdg()
// {
//     if(up.size()>down.size())
//     {
//         down.insert(*up.begin());
//         up.erase(up.begin());
//     }
//     while(down.size()>up.size()+1)
//     {
//         auto p = down.end();
//         p--;
//         up.insert(*p);
//         down.erase(p);
//     }
// }
// int main()
// {
//     int n; cin>>n;
//     char op[20];
//     while(n--)
//     {
//         scanf("%s",op);
//         if(strcmp(op,"Pop")==0)
//         {
//             if(tt<1) puts("Invalid");
//             else
//             {
//                 int x = stk[tt];
//                 tt--;
//                 auto t = down.end();
//                 t--;
//                 if(*t<x) up.erase(up.find(x));
//                 else down.erase(down.find(x));
//                 printf("%d\n",x);
//                 jdg();
//             }
//         }
//         else if(strcmp(op,"PeekMedian")==0)
//         {
//             if(tt<1) puts("Invalid");
//             else{
//                 auto t = down.end();
//                 t--;
//                 printf("%d\n",*t);
//             }
//         }
//         else{
//             int k; scanf("%d",&k);
//             stk[++tt]=k;
//             if(up.size()<1 || *up.begin()>k) down.insert(k);
//             else up.insert(k);
//             jdg();
//         }
//     }
//     return 0;
// }